Most modern computers, including those that execute instructions out-of-order and/or via a pipelined execution unit, execute instructions "speculatively". That is, instructions are executed before the instructions on which they depend have been fully executed, and quite possibly, before the outcomes of branches in the instruction stream are known. To achieve a high degree of performance, the microprocessors in these computers employ a variety of techniques to minimize the cost of erroneously predicted branches in the instruction stream. These techniques usually involve some form of "branch prediction". Branch prediction is a means of optimizing for the outcome of a branch instruction which is mostly likely to occur (either "taken" or "not taken").
Typically, a branch prediction will be based on one of two types of information: 1) static prediction information, or 2) dynamic prediction information. Static prediction information is generated prior to the execution of a computer program, and may be based on factors such as instruction type, position in the instruction stream, instruction repetition, and so on. Dynamic prediction information is generated during the execution of a computer program, and usually depends on a history of previous outcomes of a given branch and/or other branch instructions.
Dynamic prediction information is stored in a branch history table comprising a number of entries. If a branch history table was large enough, it is conceivable that a distinct history could be maintained for each branch instruction of a computer program. However, given that microprocessor chip area is a costly resource, and that branch history tables are often scaled back to make room for other important microprocessor elements, entries in a branch history table are often shared. Interference between conflicting branch histories is therefore a significant problem.
When conflicting histories share a single entry in a branch history table, the history for any given branch instruction is often corrupted by other branch instructions, thereby resulting in a mispredicted branch outcome. When a branch outcome is mispredicted, serious and costly consequences result. For example, instruction pipelines may stall, instruction execution units may be halted, caches and registers may need to be flushed, and so on. All of these consequences result in unacceptable delays.
It is therefore a primary object of this invention to provide methods and apparatus which reduce interference in a branch history table of a microprocessor, thereby yielding 1) more accurate branch predictions, and consequently 2) fewer delays caused by erroneously predicted branches.